Notes - Pages 159-209

Centrality
degree centrality - simple count of edges. Eigenvector centrality - proportional centrality related to the neighbors of a node, for positive centrality scores the largest eigenvector is used $Ax = \kappa x$ with $\kappa$ equal to largest eigenvalue which we know exists due to the Perron-Frobenius theorem. Cant use eigenvector centrality on acyclic graphs -> 0.
160
Katz Centrality
set the eigenvector centrality so that no node has zero centrality thus it wont zero out connected nodes. Linearize the eigenvector sum.
164
PageRanke Centrality
Katz, divided by the max(out edge count, 1).
166
Authorities and Hubs - definitions
authorities - nodes that contain useful information, hubs point to authorities.
168
Betweeness Centrality
Measures the number of shortest paths between two nodes a node belongs to. Higher betweeness nodes are sometimes called brokers. Borgatti[76] reference.
175
k-cores and k-components
k-cores are a relaxation technique on cliques. a core is a set of nodes such that each node is connected to alteast k-nodes in the same group. This naturally creates a set such that $core_{k+1}$ is a subset of the $k^{th}$ core into whats called a core-periphery structure. This structure is mirrored in k-components, which are components with k-paths between any two nodes.
175-183
clustering coeffecient (C)
measure of transitivity in a network. If C is 1 then all components are cliques. Lattices and trees are examples of $C = 0$. A simple way to compute this measure is $\frac{number~of~triangls~*~6}{number~of~paths~of~length~2}$
175-183
Redudancy
The average number of connections from the neighbors of a node to the other neighbors of the same node. The local clustering coeffecient can be calculated as a normalized version of the redundancy for a node.
188
Structural Stability and Clusterability
even number of negative weights have structural stability and are clusterable
192
Similarity
Structural equivalence - share same neighbors, regular equivlance - neighbors themselves are similar... Structural is measured by cosine similarity (Saltons similarity) is the most used measure $\frac{n_{ij}}{\sqrt{k_ik_j}}$ where n is the common/shared neighbor count and ki and kj are the individual neighbor counts
195-197

Transitivity is if node x is connected to node y, and node y to node z, then node x is connected to node z... however the relations the edges signifiy may not hold (A friend may not know my other friend, even if it is more likely than general population). For this reason a clique is the only graph structure that has perfect (i.e. mathematical) transitivity.

Reciprocity - number of edges that two nodes link to each other over the total number of edges

Associative mixing, modularity measure - if its postivie then there is associative mixing, negative disassociative mixing. Different types include scalar/ordered and degree associative mixing.